Có thể xây dựng cây hậu tố cho xâu S {\displaystyle S} độ dài n {\displaystyle n} trong thời gian Θ ( n ) {\displaystyle \Theta (n)} , nếu bảng chữ cái có kích thước đa thức (và do đó cũng đúng khi bảng chữ cái có kích thước hằng số).[5]Với bảng chữ cái lớn hơn, đa số thời gian chạy là cho việc sắp xếp các chữ cái để đưa chúng về kích thước O ( n ) {\displaystyle O(n)} ; trong trường hợp tổng quát, việc này tốn thời gian O ( n log ⁡ n ) {\displaystyle O(n\log n)} .Các kết quả dưới đây là cho trường hợp kích thước bảng chữ cái là hằng số.

Giả sử đã có cây hậu tố cho xâu S {\displaystyle S} độ dài n {\displaystyle n} , hoặc đã có cây hậu tố tổng quát cho tập hợp các xâu D = { S 1 , S 2 , … , S K } {\displaystyle D=\{S_{1},S_{2},\dots ,S_{K}\}} với tổng độ dài n = | n 1 | + | n 2 | + ⋯ + | n K | {\displaystyle n=|n_{1}|+|n_{2}|+\cdots +|n_{K}|} . Ta có thể:

• Tìm kiếm xâu con:
  • Kiểm tra xem xâu P {\displaystyle P} độ dài m {\displaystyle m} có phải xâu con hay không trong thời gian O ( m ) {\displaystyle O(m)} ([6] trang 92).
  • Tìm lần xuất hiện đầu tiên của một trong các mẫu P 1 , … , P q {\displaystyle P_{1},\dots ,P_{q}} với tổng độ dài m {\displaystyle m} trong thời gian O ( m ) {\displaystyle O(m)} .
  • Tìm tất cả z {\displaystyle z} lần xuất hiện của các mẫu P 1 , … , P q {\displaystyle P_{1},\dots ,P_{q}} với tổng độ dài m {\displaystyle m} trong thời gian O ( m + z ) {\displaystyle O(m+z)} ([6] trang 123).
  • Tìm kiếm biểu thức chính quy P trong thời gian kì vọng dưới tuyến tính theo n {\displaystyle n} ([7]).
  • Tìm cho mọi hậu tố của mẫu P {\displaystyle P} , độ dài chuỗi giống nhau dài nhất giữa tiền tố của P [ i … m ] {\displaystyle P[i\dots m]} và các xâu con của D {\displaystyle D} trong thời gian Θ ( m ) {\displaystyle \Theta (m)} ([6] trang 132).
• Xác định tính chất của xâu:
  • Tìm xâu con chung dài nhất của xâu S i {\displaystyle S_{i}} và S j {\displaystyle S_{j}} trong thời gian Θ ( n i + n j ) {\displaystyle \Theta (n_{i}+n_{j})} ([6] trang 125).
  • Tìm tất cả z {\displaystyle z} cặp tối đại trong thời gian Θ ( n + z ) {\displaystyle \Theta (n+z)} ([6] trang 144).
  • Tìm mọi phân tích Lempel–Ziv trong thời gian Θ ( n ) {\displaystyle \Theta (n)} ([6] trang 166).
  • Tìm xâu con lặp lại dài nhất trong thời gian Θ ( n ) {\displaystyle \Theta (n)} .
  • Tìm xâu con lặp lại nhiều lần nhất với chiều dài ít nhất một số cho trước trong thời gian Θ ( n ) {\displaystyle \Theta (n)} .
  • Tìm xâu ngắn nhất dùng bảng chữ cái Σ {\displaystyle \Sigma } mà không xuất hiện trong D {\displaystyle D} , trong thời gian O ( n + z ) {\displaystyle O(n+z)} , nếu có z {\displaystyle z} xâu như vậy.
  • Tìm xâu con ngắn nhất chỉ xuất hiện đúng một lần trong thời gian Θ ( n ) {\displaystyle \Theta (n)} .
  • Tìm, với mỗi i {\displaystyle i} , xâu con ngắn nhất của S i {\displaystyle S_{i}} không xuất hiện ở chỗ nào khác trong D {\displaystyle D} trong thời gian Θ ( n ) {\displaystyle \Theta (n)} .

Có thể xây dựng một cấu trúc dữ liệu hỗ trợ cho cây hậu tố trong thời gian Θ ( n ) {\displaystyle \Theta (n)} để tìm tổ tiên chung thấp nhất của các nút trong thời gian hằng số([6] chương 8). Khi đó có thể:

• Tìm tiền tố chung dài nhất của hai hậu tố S i [ p . . n i ] {\displaystyle S_{i}[p..n_{i}]} và S j [ q . . n j ] {\displaystyle S_{j}[q..n_{j}]} trong thời gian Θ ( 1 ) {\displaystyle \Theta (1)} ([6] trang 196).
• Tìm mẫu P độ dài m với không quá k lỗi sai trong thời gian O ( k n + z ) {\displaystyle O(kn+z)} , trong đó z là số lần xuất hiện ([6] trang 200).
• Tìm tất cả z {\displaystyle z} xâu đối xứng tối đại trong Θ ( n ) {\displaystyle \Theta (n)} ([6] trang 198), hoặc thời gian Θ ( g n ) {\displaystyle \Theta (gn)} nếu cho phép bỏ qua g {\displaystyle g} ký tự, hoặc Θ ( k n ) {\displaystyle \Theta (kn)} nếu cho phép k {\displaystyle k} lỗi sai ([6] trang 201).
• Tìm tất cả z {\displaystyle z} xâu lặp lại hai lần liên tiếp nhau trong thời gian O ( n log ⁡ n + z ) {\displaystyle O(n\log n+z)} , và nếu cho phép k lỗi sai thì thời gian là O ( k n log ⁡ ( n / k ) + z ) {\displaystyle O(kn\log(n/k)+z)} ([6] trang 204).
• Tìm xâu con chung dài nhất của ít nhất k {\displaystyle k} xâu trong D {\displaystyle D} với k = 2 , … , K {\displaystyle k=2,\dots ,K} trong thời gian Θ ( n ) {\displaystyle \Theta (n)} ([6] trang 205).
• Tìm xâu con đối xứng dài nhất của một xâu cho trước (bằng cây hậu tố của xâu cho trước và xâu ngược lại) trong thời gian tuyến tính ([6] trang 197–199).